package zwp.exercise.intereview.base.sort.QuickSort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/29 11:43
 * @description 快速排序-双边循环复习
 */
public class QuickSort2Review {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};

        int l = 0;
        int r = array.length - 1;



        recursion(array, l, r);
    }

    private static void recursion(int[] array, int l, int r) {
        if (l>=r){
            return;
        }
        int sort = sort(array, l, r);
        recursion(array,l,sort-1);
        recursion(array,sort+1,r);
    }

    private static int sort(int[] array, int l, int r) {

        int i = l;
        int j = r;

        int value = array[r];

            while (i < j) {
                while (i < j && array[i] < value) {
                    i++;
                }
                while (i < j && array[j] >= value) {
                    j--;
                }
                exchange(array, i, j);
            }

        exchange(array,r,j);
        System.out.println(Arrays.toString(array));
        return i;
    }

    private static void exchange(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
